/**
 * @projectName study-note
 * @package simple
 * @className simple.Fibonacci
 */
package simple;

/**
 * Fibonacci
 * @description 斐波那契数列
 * @author answer_wx
 * @date 2022/7/8 21:24
 * @version 1.0
 */
public class Fibonacci {
    // 1 1 2 3 5 8

    /**
     * 递归
     * @param n
     * @return
     */
    public static int fibonacci(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static int fibonacci_1(int n) {
        int a1 = 1, a2 = 1, a3 = 0;
        if (n == 0 || n == 1) {
            return 1;
        }
        for (int i = 2; i <= n; i++) {
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }

    public static int fibonacci_2(int n) {
        int[] a = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            if (i == 0 || i == 1) {
                a[i] = 1;
            } else {
                a[i] = a[i - 1] + a[i - 2];
            }
        }
        return a[n];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(5));
        System.out.println(fibonacci_1(5));
        System.out.println(fibonacci_2(5));
    }
}